<?php
/**
 * @title 39. 组合总和 - 递归
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        /**
         * @since 2020-07-16 排序
         */
        sort($candidates);

        /**
         * @since 2020-07-16 最大数量
         */
        $maxCount = intval($target/$candidates[0]);

        /**
         * @return
         */
        return self::find($candidates, $target, 0, $maxCount, []);
    }

    /**
     * @title 递归求解
     * @author start2004
     * @since 2020-07-16 Created
     *
     * @param array $candidates
     * @param int $target
     * @param int $start
     * @param int $maxCount
     * @param array $result
     * @return array|bool
     */
    function find($candidates = [], $target = 0, $start = 0, $maxCount = 0, $result = []){
        /**
         * @since 2020-07-16 不存在下个元素
         */
        if($start == count($candidates)-1){
            /**
             * @since 2020-07-16 当前元素若不能凑齐target, 该路径无解
             */
            if($target == $candidates[$start]*$maxCount){
                return self::merge($result, $candidates[$start], $maxCount);
            } else {
                return [];
            }
        } else {
            $list = [];

            /**
             * @since 2020-07-16 元素数量由maxCount到0
             */
            for ($c=$maxCount; $c>=0; $c--){
                $nextTarget = $target - $candidates[$start]*$c;
                if($nextTarget>0){
                    /**
                     * @since 2020-07-16 升序, 下个数都不能选1个, 后续都不可能
                     */
                    $nextMaxCount = intval($nextTarget/$candidates[$start+1]);

                    // echo "target={$target}, current=", $candidates[$start], "*{$c}, next_target={$nextTarget}, next_max_count={$nextMaxCount}", PHP_EOL;

                    if($nextMaxCount>0){
                        $rArray = self::find($candidates, $nextTarget, $start+1, $nextMaxCount, self::merge($result, $candidates[$start], $c));
                        /**
                         * @since 2020-07-16 有解
                         */
                        if($rArray){
                            $list = array_merge($list, $rArray);
                        } else {}
                    } else {
                        /**
                         * @since 2020-07-16 数组升序, 但c--, 没办法break
                         */
                        //break;
                    }
                } elseif($nextTarget == 0) {
                    $list = array_merge($list, self::merge($result, $candidates[$start], $c));
                } else {
                    /**
                     * @since 2020-07-16 数字均为正整数, 负数无解
                     */
                }
            }
        }

        /**
         * @return
         */
        return $list;
    }

    /**
     * @title 数组合并
     * @author start2004
     * @since 2020-07-16 Created
     *
     * @param array $result
     * @param int $num
     */
    function merge($result = [], $num = 0, $count = 0){
        if($count == 0){
            return $result;
        } else {
            $nums = array_fill(0, $count, $num);
            if(empty($result)){
                return [$nums];
            } else {
                $list = [];
                foreach ($result as $rArray){
                    $list[] = array_merge($rArray, $nums);
                }

                /**
                 * @return
                 */
                return $list;
            }
        }
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.15_5.php
 */
$datas = [
    // [[2], 1],
    // [[2,3,6,7],7,],
    [[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,],28],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof(2);
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->combinationSum($data[0], $data[1]);
    if(count($result)<20){
        var_dump($result);
    } else {
        var_dump(count($result));
    }
    echo str_repeat("<br>", 3);
}
$xhprof->end();
